Multi-carrier modulation is well-known in the art, and is described at length in a number of patents assigned to Amati, including U.S. Pat. Nos. 5,400,322, 5,479,447, 5,557,612, 5,519,731, and 5,596,604 to name a few. A popular line code implemented today for ADSL is based on modulating N separate sub-carriers within a particular usable frequency band of a transmission channel, in this case a digital subscriber line. A set of N sub-carriers (N=256 in a case of a T1.413 issue 2 compliant device, and some sub-set of this number in the currently proposed G.992-1 and G.992-2 standards) are individually configured with bit and energy loading according to the received SNR measured during an initialization or hand shaking procedure between an upstream (CO side) and downstream (CPE side) transceiver. The sub-carriers are then modulated according to the transmitted data and the assigned bit loading. In general, during a pre-defined interval called the symbol interval, each sub-carrier is quadrature-amplitude modulated (QAM) and the transmitted output is a superposition of all the modulated sub-carriers. In the case of T1.413 and G.992-x standards, a DMT symbol period is approximately 250 .mu.sec.
To maintain synchronization between the upstream and downstream transceivers, a variety of synchronization mechanisms are required. First, to maintain sampling clock synchronization (i.e. to make sure that the clock that operates the A/D and D/A at the CO side is the same as that at the CPE side), a pilot tone is generally dedicated and transmitted by the upstream transceiver. Second, when the received signal is sampled by the recovered clock, a correct set of samples corresponding to one transmitted symbol needs to be collected for subsequent demodulation. This process is called symbol boundary detection. Since each symbol is used to carry a certain number (B) of bits which form a data frame, a DMT symbol when viewed as an information bit stream is also called a frame. It is common to form M frames as a superframe. The purpose is to assign the same byte location in each frame for different types of overhead bytes. With the recognition of the superframe boundary, each overhead byte can be detected properly. Therefore, a third type of synchronization maintains superframe synchronization. In ADSL standards, a superframe consists of 68 data frames and one synchronization frame, which is a fixed pattern for superframe synchronization.
It is extremely important that the linked transceivers efficiently and reliably detect the correct received symbol boundary for subsequent demodulation. In general, this boundary detection needs to be done very early during the initialization or handshaking phase of the connection. With this task achieved, all further information changed via the DMT symbols can be processed.
A prior art proposal for achieving the symbol boundary during the initialization procedure in an ADSL system is performed as follows: (1) a fixed pattern, periodic, and time-domain signal x(t) (having an FFT X[n] as its frequency domain signal) is transmitted; (2) the received signal y(t) is sampled at the same clock (assuming the sampling clock is recovered) and an FFT is used to transform the time domain samples into frequency domain data Y[n]; (3) since X[n] is known, a ratio Z[n] =Y[n]/X[n] can be calculated, where Z[n] represents the channel transfer function; since y(t) is also periodic, Y[n] can have a phase shift if a different set of y(t) samples is used to compute Y[n];(4) a channel impulse response h[i] is then calculated, by taking an inverse FFT of Z[n]; note that if there is a time shift in collecting y(t) samples, there is a cyclic shift of h[i]; (5) the squares (h[i].sup.2) are summed over a cyclic range of 1+v, where v is a predefined cyclic prefix length; a cyclic prefix is a repetition of the last v samples a DMT symbol and appended to the beginning of the symbol; this cyclic prefix is a useful technique to reduce intersymbol interference and is used after the symbol boundary is detected; (6) the beginning of the cyclic range which maximizes the sum corresponds to the symbol boundary and is detected as such. For T1.413 (as well as G.992-1 and G.992-2), note that X[n] is a specified complex sequence with a value equal to .+-.1.+-.j. Accordingly, the square of its magnitude is always equal to 2. In actual practice, steps (2) and (3) are executed first to estimate the channel transfer function. A computation is then performed to insert an additional time domain equalizer (called the TEQ filter in ADSL) before the FFT input. The above steps (2) and (3) are then performed again to yield a combined channel and equalizer transfer function.
While the above algorithm is sufficient for many purposes, it has certain characteristics that make it undesirable for some applications. In particular, the computational complexity of the above approach is rather high. This is caused by the fact that a division operation must be performed, as noted in step (3). These types of calculations require more processing time from a signal processing unit and more latency time to establish the boundary synchronization. The drawbacks of such approach are even more apparent in the so-called "soft modem" applications, where processing power is at a premium because it is shared among many other competing agents.